/*
--------------------------------------------------------------------------------
				Ak-Lib. 
			 Project       	: Ak-Lib
			 Group         	: Ak-Lib R&D Team
			 Author        	: Ocean.Wang
			 Create Date 	: 05-01-2010
--------------------------------------------------------------------------------
Code Name 	:  A.K 	~v~
Description	:  Yet Another Cross-Platform Lib.
Cautions    	:
--------------------------------------------------------------------------------
Change History:
Version		: 0.1
Building 		: 05/01/10
10-05.01 first draft, build, debug and test.
--------------------------------------------------------------------------------
*/
#include "ak_tree.h"

/* -----------------------------------------------------------------------------
** Red - Black Tree.
** 
*/
#define	RB_RED		0
#define	RB_BLACK	1

#define RB_ROOT						(struct _t_rbroot) {NULL}
#define RB_EMPTY_ROOT(rRoot)		((rRoot)->rb_node == NULL)
#define RB_EMPTY_NODE(rNode)		(rb_parent(rNode) == (rNode))

#define rb_root(rRoot)				((rRoot)->rb_node)
#define rb_parent(rNode)  			((struct _t_rbnode *)(unsigned long)((rNode)->rb_pcolor & ~3))
#define rb_color(rNode)   			((rNode)->rb_pcolor & 1)
#define rb_is_red(rNode)  			(!rb_color(rNode))
#define rb_is_black(rNode) 			(rb_color(rNode))

#define rb_set_red(rNode)  	\
do{\
	(rNode)->rb_pcolor &= ~1; \
}while (0)

#define rb_set_black(rNode)	\
do{\
	(rNode)->rb_pcolor |= 1; \
}while (0)

static __inline void rb_set_color(_t_rbnode *rNode, int color)
{
	rNode->rb_pcolor = (rNode->rb_pcolor & ~1) | color;
}

static __inline void rb_link_node(_t_rbnode * 	rNode, 
									_t_rbnode * 	rParent,
									_t_rbnode ** 	rLink)
{
	rNode->rb_pcolor 	= (unsigned long long)(unsigned long)(rParent);
	rNode->rb_left 		= rNode->rb_right = NULL;
	*rLink = rNode;
}


static 	void 	_rb_rotate_left(_t_rbroot * rRoot, _t_rbnode * rNode)
{
	_t_rbnode *rRight  = rNode->rb_right;
	_t_rbnode *rParent = rb_parent(rNode);

	if( (rNode->rb_right = rRight->rb_left) )
		rb_set_parent(rRight->rb_left, rNode);
	
	rRight->rb_left = rNode;

	rb_set_parent(rRight, rParent);

	if (rParent){
		if (rNode == rParent->rb_left)
			rParent->rb_left = rRight;
		else
			rParent->rb_right = rRight;
	}
	else
		rb_root(rRoot) = rRight;
	
	rb_set_parent(rNode, rRight);
}


static 	void 	_rb_rotate_right(_t_rbroot *rRoot, _t_rbnode *rNode)
{
	_t_rbnode *rLeft  	= rNode->rb_left;
	_t_rbnode *rParent 	= rb_parent(rNode);

	if( (rNode->rb_left = rLeft->rb_right) )
		rb_set_parent(rLeft->rb_right, rNode);

	rLeft->rb_right = rNode;

	rb_set_parent(rLeft, rParent);

	if (rParent){
		if (rNode == rParent->rb_right)
			rParent->rb_right = rLeft;
		else
			rParent->rb_left = rLeft;
	}
	else
		rb_root(rRoot) = rLeft;
	
	rb_set_parent(rNode, rLeft);
}


static 	void 	_rb_erase_color(_t_rbroot  *	rRoot,
								_t_rbnode  * 	rNode, 
								_t_rbnode  *	rParent)
{
	_t_rbnode *rOther, *o_right, *o_left;

	while ((!rNode || rb_is_black(rNode)) && rNode != rb_root(rRoot))	{
		if (rParent->rb_left == rNode){
			
			rOther = rParent->rb_right;
			if (rb_is_red(rOther)){
				rb_set_black(rOther);
				rb_set_red(rParent);
				_rb_rotate_left(rRoot, rParent);
				rOther = rParent->rb_right;
			}
			
			if ((!rOther->rb_left || rb_is_black(rOther->rb_left)) &&
			    (!rOther->rb_right || rb_is_black(rOther->rb_right)))	{
				rb_set_red(rOther);
				rNode = rParent;
				rParent = rb_parent(rNode);
			}
			else{
				if (!rOther->rb_right || rb_is_black(rOther->rb_right)){
					
					if ((o_left = rOther->rb_left))
						rb_set_black(o_left);
					rb_set_red(rOther);
					_rb_rotate_right(rRoot, rOther);
					rOther = rParent->rb_right;
				}
				rb_set_color(rOther, rb_color(rParent));
				rb_set_black(rParent);
				
				if (rOther->rb_right)
					rb_set_black(rOther->rb_right);
				
				_rb_rotate_left(rRoot, rParent);
				rNode = rb_root(rRoot);
				break;
			}
		}

		else{
			rOther = rParent->rb_left;
			if (rb_is_red(rOther)){
				rb_set_black(rOther);
				rb_set_red(rParent);
				_rb_rotate_right(rRoot, rParent);
				rOther = rParent->rb_left;
			}
			if ((!rOther->rb_left || rb_is_black(rOther->rb_left)) &&
			    (!rOther->rb_right || rb_is_black(rOther->rb_right)))	{
				rb_set_red(rOther);
				rNode = rParent;
				rParent = rb_parent(rNode);
			}
			else {
				if (!rOther->rb_left || rb_is_black(rOther->rb_left)) {
					if ((o_right = rOther->rb_right))
						rb_set_black(o_right);
					rb_set_red(rOther);
					_rb_rotate_left(rRoot, rOther);
					rOther = rParent->rb_left;
				}
				rb_set_color(rOther, rb_color(rParent));
				rb_set_black(rParent);
				
				if (rOther->rb_left)
					rb_set_black(rOther->rb_left);
				
				_rb_rotate_right(rRoot, rParent);
				rNode = rb_root(rRoot);
				break;
			}
		}
	}
	if (rNode)
		rb_set_black(rNode);
}


static 	void 	_rb_insert_color(_t_rbroot * rRoot, _t_rbnode * rNode)
{
	_t_rbnode *rParent, *gparent, *uncle, *tmp;

	while ((rParent = rb_parent(rNode)) && rb_is_red(rParent))	{
		gparent = rb_parent(rParent);

		if (rParent == gparent->rb_left){
			{
				uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle)){
					rb_set_black(uncle);
					rb_set_black(rParent);
					rb_set_red(gparent);
					rNode = gparent;
					continue;
				}
			}

			if (rParent->rb_right == rNode) {
				_rb_rotate_left(rRoot, rParent);
				tmp = rParent;
				rParent = rNode;
				rNode = tmp;
			}

			rb_set_black(rParent);
			rb_set_red(gparent);
			_rb_rotate_right(rRoot, gparent);
		} 
		else {
			{
				uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle)){
					rb_set_black(uncle);
					rb_set_black(rParent);
					rb_set_red(gparent);
					rNode = gparent;
					continue;
				}
			}

			if (rParent->rb_left == rNode) {
				
				_rb_rotate_right(rRoot, rParent);
				tmp = rParent;
				rParent = rNode;
				rNode = tmp;
			}

			rb_set_black(rParent);
			rb_set_red(gparent);
			_rb_rotate_left(rRoot, gparent);
		}
	}

	rb_set_black(rb_root(rRoot));
}


void 	rb_erase(_t_rbroot *rRoot, _t_rbnode *rNode)
{
	_t_rbnode *child, *rParent, *rLeft, *old;
	int color;

	if (!rNode->rb_left)
		child = rNode->rb_right;
	else if (!rNode->rb_right)
		child = rNode->rb_left;
	else{
		old = rNode;

		rNode = rNode->rb_right;
		while ((rLeft = rNode->rb_left) != NULL)
			rNode = rLeft;
		
		child = rNode->rb_right;
		rParent = rb_parent(rNode);
		color = rb_color(rNode);

		if (child)
			rb_set_parent(child, rParent);
		if (rParent == old) {
			rParent->rb_right = child;
			rParent = rNode;
		} else
			rParent->rb_left = child;

		rNode->rb_pcolor = old->rb_pcolor;
		rNode->rb_right = old->rb_right;
		rNode->rb_left = old->rb_left;

		if (rb_parent(old))	{
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = rNode;
			else
				rb_parent(old)->rb_right = rNode;
		} else
			rb_root(rRoot) = rNode;

		rb_set_parent(old->rb_left, rNode);
		if (old->rb_right)
			rb_set_parent(old->rb_right, rNode);
		goto color;
	}

	rParent = rb_parent(rNode);
	color = rb_color(rNode);

	if (child)
		rb_set_parent(child, rParent);

	if (rParent){
		if (rParent->rb_left == rNode)
			rParent->rb_left = child;
		else
			rParent->rb_right = child;
	}
	else
		rb_root(rRoot) = child;

 color:
	if (color == RB_BLACK)
		_rb_erase_color(rRoot, child, rParent);
}


_t_rbnode *	rb_first(_t_rbroot *rRoot)
{
	struct _t_rbnode	*n;

	n = rb_root(rRoot);
	if (!n)
		return NULL;

	while (n->rb_left)
		n = n->rb_left;

	return n;
}


_t_rbnode *	rb_last(_t_rbroot *rRoot)
{
	struct _t_rbnode	*n;

	n = rb_root(rRoot);
	if (!n)
		return NULL;
	while (n->rb_right)
		n = n->rb_right;
	return n;
}


 _t_rbnode *	rb_next(_t_rbnode *rNode)
{
	struct _t_rbnode *rParent;

	if (rb_parent(rNode) == rNode)
		return NULL;

	/* If we have a rRight-hand child, go down and then rLeft as far
	   as we can. */
	if (rNode->rb_right) {
		rNode = rNode->rb_right; 
		while (rNode->rb_left)
			rNode=rNode->rb_left;
		return rNode;
	}

	/* No rRight-hand children.  Everything down and rLeft is
	   smaller than us, so any 'next' rNode must be in the general
	   direction of our rParent. Go up the tree; any time the
	   ancestor is a rRight-hand child of its rParent, keep going
	   up. First time it's a rLeft-hand child of its rParent, said
	   rParent is our 'next' rNode. */
	while ((rParent = rb_parent(rNode)) && rNode == rParent->rb_right)
		rNode = rParent;

	return rParent;
}


_t_rbnode *	rb_prev(_t_rbnode *rNode)
{
	struct _t_rbnode *rParent;

	if (rb_parent(rNode) == rNode)
		return NULL;

	/* If we have a rLeft-hand child, go down and then rRight as far
	   as we can. */
	if (rNode->rb_left) {
		rNode = rNode->rb_left; 
		while (rNode->rb_right)
			rNode=rNode->rb_right;
		return rNode;
	}

	/* No rLeft-hand children. Go up till we find an ancestor which
	   is a rRight-hand child of its rParent */
	while ((rParent = rb_parent(rNode)) && rNode == rParent->rb_left)
		rNode = rParent;

	return rParent;
}


void 	rb_replace(_t_rbroot 	* rRoot,
					_t_rbnode 	* rOld, 
					_t_rbnode 	* rNew)
{
	struct _t_rbnode *rParent = rb_parent(rOld);

	/* Set the surrounding nodes to point to the replacement */
	if (rParent) {
		if (rOld == rParent->rb_left)
			rParent->rb_left = rNew;
		else
			rParent->rb_right = rNew;
	} else {
		rb_root(rRoot) = rNew;
	}
	
	if (rOld->rb_left)
		rb_set_parent(rOld->rb_left, rNew);
	
	if (rOld->rb_right)
		rb_set_parent(rOld->rb_right, rNew);

	/* Copy the pointers/colour from the victim to the replacement */
	*rNew = *rOld;
}


_t_rbnode * 	rb_find(_t_rbroot * rRoot, _t_rbnode * rNode,  int (*fCmp)())
{
	_t_rbnode * rTmp;
	int 		rComp;
	rTmp = rb_root(rRoot);
	while(rTmp){
		rComp = (fCmp)(rNode, rTmp);
		#if 0
		switch(rComp){
			case _TREE_LESS:
				rTmp = rTmp->rb_left;
				break;
			case _TREE_EQUAL:
				return rTmp;
				break;
			case _TREE_GREAT:
				rTmp = rTmp->rb_right;
				break;
			default:
				return NULL;
				break;
		}
		#else
		if(rComp < 0){
			rTmp = rTmp->rb_left;
		}
		else if(rComp > 0){
			rTmp = rTmp->rb_right;
		}
		else
			return rTmp;
		#endif
	}

	return NULL;
}


_t_rbnode * 	rb_insert(_t_rbroot * rRoot, _t_rbnode * rNode, int (*fCmp)())
{
	
	_t_rbnode **rLink 	= &(rb_root(rRoot));
	_t_rbnode * rParent	= NULL;
	int 		rComp;
	
	while (*rLink) {
		rParent = *rLink;
		rComp 	= (fCmp)(rNode, rParent);
		#if 0
		switch(rComp){
			case _TREE_LESS:
				rLink = &((*rLink)->rb_left);
				break;
			case _TREE_EQUAL:
				return rParent;
				break;
			case _TREE_GREAT:
				rLink = &((*rLink)->rb_right);
				break;
			default:
				return NULL;
				break;
		}
		#else
		if(rComp < 0){
			rLink = &((*rLink)->rb_left);
		}
		else if(rComp > 0){
			rLink = &((*rLink)->rb_right);
		}
		else{
			return rParent;
		}
		#endif
	}
	
	rb_link_node(rNode, rParent, rLink);
	_rb_insert_color(rRoot, rNode);
	return NULL;
}



